/**
 *给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
 *
 * 返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。
 *
 * 子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
 *https://leetcode.cn/problems/longest-subsequence-with-limited-sum/description/
 */
class AnswerQueries {
    public int[] answerQueries(int[] nums, int[] queries) {
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = 1;i<len;i++) {
            nums[i]+=nums[i-1];
        }
        int n = queries.length;
        int[] ans = new int[n];
        for(int i = 0;i<n;i++) {
            ans[i] = search(nums,queries[i]);
        }
        return ans;
    }

    private int search(int[] nums,int x)
    {
        //寻找右边界
        int left = 0;
        int right = nums.length;
        while(left < right) {
            int mid = left + (right-left)/2;
            if(nums[mid] > x) {
                right = mid;
            } else if(nums[mid] < x) {
                left = mid +1;
            } else {
                left = mid +1;
            }
        }
        return left;
    }
}